Computer-aided design (CAD) software allows a user to construct and manipulate complex three-dimensional (3D) models. A number of different modeling techniques can be used to create a 3D model. These techniques include solid modeling, wire-frame modeling, and surface modeling. Solid modeling techniques provide for topological 3D models, where the 3D model is a collection of interconnected topological entities (e.g., vertices, edges, and faces). The topological entities have corresponding supporting geometrical entities (e.g., points, trimmed curves, and trimmed surfaces). The trimmed surfaces correspond to the topological faces bounded by the edges. Wire-frame modeling techniques, on the other hand, can be used to represent a model as a collection of simple 3D lines, whereas surface modeling can be used to represent a model as a collection of exterior surfaces. CAD systems may combine these and other modeling techniques, such as parametric modeling techniques. Parametric modeling techniques can be used to define various parameters for different features and components of a model, and to define relationships between those features and components based on relationships between the various parameters.
Surfaces are represented in CAD systems using several techniques. The techniques include the definition of surfaces as parametric surfaces, mesh surfaces, subdivision surfaces, and implicit surfaces.
A parametric surface is a deformation of a parameter space, typically that space is rectangular. Computer-aided modeling software commonly uses low-degree algebraic deformations, resulting in various spline and quadric surfaces. For some types of parametric surfaces, a set of control points defines the surface shape.
A mesh surface, also referred to as a tessellated surface, is a connected set of polygons, which are often triangular polygons. A mesh surface cannot represent a smooth surface exactly. However, certain basic operations applied to mesh surfaces are easy to implement and efficient to execute. Such basic operations include computing a bounding box and intersecting a mesh surface with one or more simple objects.
A subdivision surface is defined as the limit of a sequence of meshes. Each mesh in such a sequence is obtained by subdividing the previous mesh in the sequence according to one of several subdivision methods, which are know by those who are skilled in the art. An initial control mesh (i.e., the first mesh in the sequence) is thus sufficient to specify the subdivision surface. Although the initial control mesh is not smooth, the resulting subdivision surface is smooth, and the degree of smoothness of the resulting subdivision surface depends on the subdivision method chosen. If desired, the subdivision method can be adjusted to ensure that certain edges remain sharp.
An implicit surface is defined as the set of points that satisfy the expression F(x, y, z)=0. If F is a smooth function, the surface will usually be smooth. Spheres, tori, and ellipsoids are some of the surfaces that can be represented as implicit surfaces.
In general, state-of-the-art computer graphics hardware is optimized to render mesh surface representations, and therefore, some surface representations are routinely converted to mesh surfaces for rendering. Approximating a parametric surface with a mesh is generally straightforward because a mesh can be constructed on the parametric space and a deformation of the surface can be evaluated on the mesh vertices. Converting a subdivision surface to a mesh is also generally straightforward, since the sequence of meshes converges to the subdivision surface very quickly. Approximating an implicit surface with a mesh is generally difficult; however, methods have been developed to approximate an implicit surface.
To deform a spline or a subdivision surface, the surface control mesh is modified. The coarser the control mesh is, the more limited is the ability to control modifications to the surface. However, a finer control mesh (which may be necessary to produce small features), increases the size of the control mesh, and therefore, requires more memory to store the surface and a greater number of computations to transform the surface.
Another deformation approach is to deform the space in which the surface is located. Typically, the 3D space is tessellated into a cubic mesh and the cubic mesh is deformed. Based on the deformed mesh, a deformation is computed for the entire space and applied to the surface, as described in an article titled “A Framework for Geometric Warps and Deformations” by Tim Milliron et al., ACM Transactions on Graphics, Vol. 21, No. 1, January 2002, pp. 20-51. The deformation may be constrained to only affect a portion of the entire space, as described in an article titled “General Constrained Deformations Based on Generalized Metaballs” by Xiaogang Jin et al., Pacific Conference on Computer Graphics and Applications 1998, pp. 115-124.
One drawback of defining a space deformation is that deforming the space in which the surface is located is not intuitive because the objective is to deform the surface not the space in which the surface resides. Additionally, if the space deformation is applied to vertices of a mesh, sharp edges of the mesh may be exaggerated because the angles between adjacent polygons may increase. Applying the space deformation to the mesh polygons may require reapproximating the result by another mesh. Reapproximating the result with a refinement of the original mesh often leads to a deterioration of the polygon aspect ratios. Furthermore, if the space deformation is applied to a spline, converting the resulting surface back into a spline may be computationally costly and the smoothness of the surface may not be maintained. Generally, the smoothness constraints between surface patches can be maintained only approximately.
Many commercially available 3D CAD systems have free-form surface manipulation capabilities. Such capabilities are usually constrained by representing the surfaces internally as non-uniform rational b-spline (NURBS) surfaces. Thus, manipulation controls are often restricted to particular points or curves of the surfaces. The user, therefore, is limited in his or her ability to form a desired shape. Some systems can allow an arbitrary point or curve as a manipulation control. For example, the SolidWorks® 2004 software product, available from SolidWorks Corporation of Concord, Mass., enables one or more surfaces to be deformed using an arbitrary point or curve as a manipulation control. Then, resulting surfaces are approximated with NURBS surface patches. Achieving the desired accuracy of shape and smoothness between surface patches, in general, leads to high density control grids and makes such surfaces computationally expensive for subsequent operations.
Many users of 3D CAD systems are skilled in 3D modeling techniques and design 3D models professionally. These experienced users understand how to manipulate control points and meshes used to define a surface, and how to manipulate vertices and edges that are surface entities. A 3D CAD system that provides a simple and intuitive means to create and modify the shape of 3D models of various complexities would be advantageous for those not skilled in 3D modeling techniques as well as for those that are. A 3D CAD system that allows users to interactively deform complex models by direct manipulation of an arbitrary point, curve, or surface area, while preserving the smoothness of the surface throughout the model, could enable users to create smooth shapes in a natural, fast, and simple way, and thereby enhance the capabilities and ease of use of a 3D CAD system.